#define _CRT_SECURE_NO_WARNINGS
// Exp2-3_CircularSeqQueue_Expandable

// 特别注意：
// 当队列从逻辑上跨越数组边界时，数组容量的扩充比较麻烦；
// 除了扩充数组容量，还应该把队头到MAX-1这段内容复制到新空间的末尾。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define QUEUE_INIT_LENGTH 4        // 动态数组的初始长度
#define QUEUE_INCREMENT 3        // 动态数组长度不够时，每次增加的长度
#define STU_ID_MAXLEN 16
#define STU_NAME_MAXLEN 20

// 学生结构体
typedef struct {
	char stuId[STU_ID_MAXLEN];
	char name[STU_NAME_MAXLEN];
	char gender;
	float score;
} Stu;

// 动态顺序队列结构体
typedef struct {
	Stu *base;            // 存放学生的动态数组的起始地址，数组大小可以扩充，因此称其为“动态”
	int queueSize;        // 当前顺序队列中数组单元的个数
	int front;            // 指示队头元素的位置
	int rear;            // 指示队尾元素的位置
} CircularSeqQueue;

Stu *ps;
int stuNum;

// Get alternative all students' data
void loadAllStudent() {
	FILE *fp;
	int i = 0;

	if ((fp = fopen("allStu.dat", "rb")) == NULL) {
		printf("Cannot open the data file, failed to save the student information!");
		return;
	}

	// 开始读文件，先读人数，根据人数开辟空间的大小
	fread(&stuNum, sizeof(int), 1, fp);
	ps = (Stu *)malloc(sizeof(Stu)*stuNum);

	while (i < stuNum) {
		fread(&(ps[i]), sizeof(Stu), 1, fp);
		i++;
	}
	// fread(ps, sizeof(Stu), stuNum, fp);

	fclose(fp);
}

void menu() {
	printf("\n\t***Expandable Circular Sequence Queue(Space can be expanded dynamically)***\n");
	printf("\t*     1 Choose a student to be placed in the queue                        *\n");
	printf("\t*     2 Take a student out of the queue                                   *\n");
	printf("\t*     3 Read the front and rear elements of the queue                     *\n");
	printf("\t*     4 Show all the students in the queue                                *\n");
	printf("\t*     0 Save & Exit                                                       *\n");
	printf("\t***************************************************************************\n");
	printf("\tPlease select a menu item:");
}

/*  Check whether the file stu2-3.dat exist in the current directory.
    If it exists, the data will be read from it to construct a Circular Sequence Queue.
*/
void init(CircularSeqQueue &csq) {
	FILE *fp;
	Stu stmp;
	int i;

	/*  给动态数组开辟初始的内存空间，并初始化为空队列；*/
	csq.base = (Stu *)malloc(sizeof(Stu)*QUEUE_INIT_LENGTH);

	// 设置顺序队列中动态数组的初始长度为MAX
	csq.queueSize = QUEUE_INIT_LENGTH;

	// 设置顺序队列的队头和队尾同时为QUEUE_INIT_LENGTH-1，表示队列为空
	// 注意：这样设置的话，进队时最好先加后进；出队时最好先加后出；
	// front始终指示队头元素前面那个空的单元，rear始终指示队尾元素
	csq.front = csq.rear = csq.queueSize - 1;

	// 打开文件
	if ((fp = fopen("stu2-3.dat", "rb")) == NULL)
		return;

	// 开始读文件
	i = 0;
	fread(&stmp, sizeof(Stu), 1, fp);        // 先尝试着读第一个学生

	while (!feof(fp)) {                      // 检测文件尚未结束，则说明读到了一个学生
		if (i <= csq.queueSize - 2) {
			csq.base[i] = stmp;                    // 将读到的学生stmp复制到顺序队列中base数组的i号单元
			i++;
			fread(&stmp, sizeof(Stu), 1, fp);    // 从文件读下一个学生的同时，执行i++
		} else {
			// 必须先扩充顺序队列中动态数组base的空间，然后再继续;
			// 给顺序队列中的动态数组增加LISTINCREMENT个单元的空间
			csq.base = (Stu *)realloc(csq.base, (csq.queueSize + QUEUE_INCREMENT) * sizeof(Stu));
			csq.queueSize = csq.queueSize + QUEUE_INCREMENT;
		}
	}

	csq.front = csq.queueSize - 1;    // 初始化时，要确保csq.front始终指示数组最后的那个单元
	if (0 == i)
		csq.rear = csq.queueSize - 1;
	else
		csq.rear = i - 1;        // 读到的学生个数i再减一，即为队尾元素的下标

	// 关闭文件
	fclose(fp);
}

/* 获取一个学生的信息 */
Stu getAStudent() {
	// 生成一个[0, stuNum-1]的随机数
	int r = rand() % stuNum;
	return ps[r];
}

/* 进队一个学生e到顺序队列csq中 */
int inQueue(CircularSeqQueue &csq, Stu e) {
	char choice, c;

	// 如果动态数组中尚有空闲空间，则可以直接进队列;
	if((csq.rear-csq.front+csq.queueSize)%csq.queueSize < csq.queueSize-1) {
		csq.rear = (csq.rear+1) %csq.queueSize ;
		csq.base[csq.rear] = e;
		return 1;
	}
	// csq.queueSize是数组中的单元个数，其中最多可以存放csq.queueSize-1个元素；
	// 而(csq.rear-csq.front+csq.queueSize)%csq.queueSize是队列中当前元素的个数。
	// 队头“指针”csq.rear先自增，然后学生进队到csq.rear指示的位置

	// 如果动态数组中已满，则可以先扩充空间，然后才能进队列
	// fflush(stdin);
	while ((c = getchar()) != '\n' && c != EOF);
	printf("The array space of the current circular sequence queue is full. Do you need to expand the space?(Press Y or y to expand, press any key to cancel the expansion)\n");
	choice = getchar();

	if ('Y' != choice && 'y' != choice)
		return 0;

	// 给顺序队列中的动态数组增加QUEUE_INCREMENT个单元的空间
	csq.base = (Stu *)realloc(csq.base, (csq.queueSize + QUEUE_INCREMENT) * sizeof(Stu));
	csq.queueSize = csq.queueSize + QUEUE_INCREMENT;

	// 如果队列不为空（如果队列为空，无需重设队头队尾指针，也没有元素需要移动）

	if(csq.front == csq.queueSize - QUEUE_INCREMENT -1) {
		csq.front = csq.front + QUEUE_INCREMENT ;

	} else if(csq.front > csq.rear) {
		int i;
		for(i=csq.queueSize-QUEUE_INCREMENT-1; i>=csq.front+1 ; i-- ) {
			csq.base[i + QUEUE_INCREMENT] = csq.base[i] ;
		}
		csq.front = csq.front + QUEUE_INCREMENT ;

		// csq.rear = (csq.rear+1) %csq.queueSize ;
		//csq.base[csq.rear] = e;
		//return 1;
	}
	// 如果队列中的元素“跨越了”数组最后那个单元和0号单元之间的边界
	// 则需要将队头至csq.queueSize-1号单元之间的所有元素移动到新空间的末尾。
	// 将csq.queueSize-QUEUE_INCREMENT-1至csq.front+1号单元之间的元素依次后移QUEUE_INCREMENT个单元
	// 队尾“指针”csq.rear先自增，然后学生进队到csq.rear指示的位置
	// 进队成功，返回1；
	printf("The array space of the current circular sequence queue has been expanded to %d, it is ready to queue!\n",csq.queueSize);
	// 队尾“指针”csq.rear先自增，然后学生进队到csq.rear指示的位置
	inQueue(csq, e);
	return 1;


}

/* 从顺序队列中出队列一个学生 */
int outQueue(CircularSeqQueue &csq, Stu &e) {
	// 队列不为空，才有元素可以出队
	if(csq.front !=csq.rear) {
		csq.front = (csq.front +1)%csq.queueSize;
		e =csq.base[csq.front];
		// 出队成功，返回1
		return 1;
	} else
		return 0;

	// 队列为空，出队失败，返回0
}

/* 读取队头和队尾学生的信息 */
int readFrontRear(CircularSeqQueue &csq, Stu &ef, Stu &er) {
	// 队列不为空，才有队头和队尾元素
	if(csq.front !=csq.rear) {
		ef =csq.base[(csq.front+1)%csq.queueSize];
		er = csq.base[csq.rear];
		return 1;
	}
	// csq.front始终指向队头元素前面那个空的单元
	else
		return 0;

	// 获取队头队尾元素失败，返回0
}

// 获取字符串中中文字符的个数
int getNumOfChineseChar(char *str) {
	int nameLen = strlen(str);
	// 每输出1个汉字，会占2个英文字符的位置，但是UTF8编码为3Bytes
	// 因此每多输出一个汉字，前面会少输出一个空格，应补足才能对齐。
	// 先统计字符串中汉字的个数chineseCount
	int chineseCount = 0, j;
	for (j = 0; j < nameLen; j++) {
		if ((unsigned int)(str[j]) > 128) {
			chineseCount++;
		}
	}
	chineseCount /= 3;  // 每个汉字的UTF-8编码为3个字节

	return chineseCount;
}

/* 显示所有学生的信息 */
void showQueue(CircularSeqQueue csq) {
	int i;

	if(csq.front != csq.rear) {
		printf("The number of cells in the circular sequence queue is %d, and the number of elements in the current sequence queue is %d.\n", csq.queueSize, (csq.rear - csq.front + csq.queueSize) % csq.queueSize);
		printf("The information of all students from front to rear in the circular sequence queue is as follows!\n");
		printf("-----------------------------------------------------------------\n");
		printf("%9s%15s%19s%9s%10s\n", "Remark", "StuID    ", "Name", "Gender", "Score");
		printf("-----------------------------------------------------------------\n");

		// 分两种情况讨论
		if(csq.front < csq.rear || csq.front == csq.queueSize-1) { // 如果队列中的元素“没有跨越”数组最后那个单元和0号单元之间的边界
			for(i=(csq.front+1)%csq.queueSize; i<=csq.rear; i++) {
				int j, chineseCount = getNumOfChineseChar(csq.base[i].name);

				if (i == (csq.front + 1) % csq.queueSize && i == csq.rear) {
					printf("%9s%15s", "Front/Rear", csq.base[i].stuId);
					for (j = 0; j < chineseCount; j++)
						printf(" ");
					printf("%19s%7c%12.1f\n", csq.base[i].name, csq.base[i].gender, csq.base[i].score);
				} else if (i == csq.rear) {
					printf("%9s%15s", "Rear", csq.base[i].stuId);
					for (j = 0; j < chineseCount; j++)
						printf(" ");
					printf("%19s%7c%12.1f\n", csq.base[i].name, csq.base[i].gender, csq.base[i].score);
				} else if (i == (csq.front + 1) % csq.queueSize) {
					printf("%9s%15s", "Front", csq.base[i].stuId);
					for (j = 0; j < chineseCount; j++)
						printf(" ");
					printf("%19s%7c%12.1f\n", csq.base[i].name, csq.base[i].gender, csq.base[i].score);
				} else {
					printf("%9s%15s", " ", csq.base[i].stuId);
					for (j = 0; j < chineseCount; j++)
						printf(" ");
					printf("%19s%7c%12.1f\n", csq.base[i].name, csq.base[i].gender, csq.base[i].score);
				}
			}
		} else { // 如果队列中的元素“跨越了”数组最后那个单元和0号单元之间的边界（此时队列中肯定不止一个元素）
			for(i=(csq.front+1)%csq.queueSize; i<csq.queueSize; i++) {      // 输出队头到csq.queueSize-1号单元
				int j, chineseCount = getNumOfChineseChar(csq.base[i].name);

				if (i == (csq.front + 1) % csq.queueSize) {
					printf("%9s%15s", "Front", csq.base[i].stuId);
					for (j = 0; j < chineseCount; j++)
						printf(" ");
					printf("%19s%7c%12.1f\n", csq.base[i].name, csq.base[i].gender, csq.base[i].score);
				} else {
					printf("%9s%15s", " ", csq.base[i].stuId);
					for (j = 0; j < chineseCount; j++)
						printf(" ");
					printf("%19s%7c%12.1f\n", csq.base[i].name, csq.base[i].gender, csq.base[i].score);
				}
			}

			for(i=0; i<=csq.rear; i++) {      // 输出0号单元到队尾
				int j, chineseCount = getNumOfChineseChar(csq.base[i].name);

				if (i == csq.rear) {
					printf("%9s%15s", "Rear", csq.base[i].stuId);
					for (j = 0; j < chineseCount; j++)
						printf(" ");
					printf("%19s%7c%12.1f\n", csq.base[i].name, csq.base[i].gender, csq.base[i].score);
				} else {
					printf("%9s%15s", " ", csq.base[i].stuId);
					for (j = 0; j < chineseCount; j++)
						printf(" ");
					printf("%19s%7c%12.1f\n", csq.base[i].name, csq.base[i].gender, csq.base[i].score);
				}
			}
		}
		printf("-----------------------------------------------------------------\n");
	} else
		printf("The queue is empty!\n");
}

/* 保存所有学生的信息到文件 */
void save(CircularSeqQueue csq) {
	FILE *fp;
	int i;

	// 打开文件
	if((fp=fopen("stu2-3.dat", "wb"))==NULL) {
		printf("Cannot open the data file, failed to save the student information!\n");
		exit(-1);
	}

	// 开始写文件（分三种情况讨论）
	if(csq.front < csq.rear || csq.front==csq.queueSize-1) {
		for(i=(csq.front+1)%csq.queueSize; i<=csq.rear; i++)
			fwrite(&(csq.base[i]), sizeof(Stu), 1, fp);
	} else if(csq.front > csq.rear) {
		for(i=csq.front+1; i<csq.queueSize; i++)        // 将队头到csq.queueSize-1号单元的元素写到文件
			fwrite(&(csq.base[i]), sizeof(Stu), 1, fp);

		for(i=0; i<=csq.rear; i++)        // 将0号单元到队尾的元素写到文件
			fwrite(&(csq.base[i]), sizeof(Stu), 1, fp);
	} else
		system("del stu.dat");            // 队列为空，直接删除数据文件

	// 关闭文件
	fclose(fp);

	printf("All data in the circular sequence queue has been written to the file successfully!\n");
}

int main() {
	int choice=-1, status, seed;
	char c;
	Stu e, eFront, eRear;
	CircularSeqQueue csq;    // 定义循环顺序队列csq

	system("chcp 65001");  // 设置window控制台（CMD或命令行窗口）为UTF-8格式

	// 获取备选的学生数据（在ps所指空间中，stuNum为空间单元数，即人数）
	loadAllStudent();

	// 输入随机种子（插入时，需随机选取学生数据）
	printf("Please enter a random seed:");
	scanf("%d", &seed);
	srand(seed);

	init(csq);        // 在init()函数中为其成员base开辟空间，并设置数组元素个数为0

	while(1) {
		menu();
		scanf("%d", &choice);

		switch(choice) {
			case 1:
				e = getAStudent();
				status = inQueue(csq, e);
				if (1 == status)
					printf("%s has been placed into the queue successfully!\n", e.name);
				else
					printf("The circular sequence queue is full, no element can be further queued!\n");
				break;
			case 2:
				status = outQueue(csq, e);
				if(1==status) {
					printf("The information of the student out of the queue is as follows:\n");
					printf("%15s%19s%7c%7.1f\n", e.stuId, e.name, e.gender, e.score);
				} else
					printf("The current queue is empty, no elements can exit from the queue!\n");
				break;
			case 3:
				status = readFrontRear(csq, eFront, eRear);
				if(1==status) {
					printf("The information of student in the front of the queue is as follows:\n");
					printf("%15s%19s%7c%7.1f\n", eFront.stuId, eFront.name, eFront.gender, eFront.score);
					printf("The information of student in the rear of the queue is as follows:\n");
					printf("%15s%19s%7c%7.1f\n", eRear.stuId, eRear.name, eRear.gender, eRear.score);
				} else
					printf("The current queue is empty, no front and rear element!\n");
				break;
			case 4:
				showQueue(csq);
				break;
			case 0:
				save(csq);
				exit(0);
				break;
			default:
				// If the user enters an alphabetic menu item instead of an integer,
				// the buffer needs to be emptied
				while ((c = getchar()) != '\n' && c != EOF);
				printf("\tThe menu item you entered does not exist, please select it again!\n");
		}
		choice=-1;
	}
	return 0;
}
